package com.zk.algorithm.tree;

import com.zk.algorithm.bean.TreeNode;

/**
 * 根到叶子是否有路径，和为 sum
 *
 * @author zk
 */
public class PathSum {

    // =================
    // 递归解法
    // 时间复杂度: O(N)，每个节点至多访问一次
    // =================

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;

        // 叶子节点
        if (root.left == null && root.right == null && sum - root.val == 0) return true;

        // 左树或者右树任意一个返回 true
        return hasPathSum(root.left, sum - root.val) ||
                hasPathSum(root.right, sum - root.val);
    }

}
